home *** CD-ROM | disk | FTP | other *** search
/ Internet Info 1994 March / Internet Info CD-ROM (Walnut Creek) (March 1994).iso / networking / ip / ka9q / src.arc / ALLOC.C < prev    next >
Encoding:
C/C++ Source or Header  |  1989-08-19  |  12.0 KB  |  507 lines
  1. /* memory allocation routines
  2.  *
  3.  * Adapted from alloc routine in K&R; memory statistics and interrupt
  4.  * protection added for use with net package. Must be used in place of
  5.  * standard Turbo-C library routines because the latter check for stack/heap
  6.  * collisions. This causes erroneous failures because process stacks are
  7.  * allocated off the heap.
  8.  */
  9.  
  10. #include <stdio.h>
  11. #include <dos.h>
  12. #include <alloc.h>
  13. #include "global.h"
  14. #include "proc.h"
  15.  
  16. static unsigned long memfail;    /* Count of allocation failures */
  17. static unsigned long allocs;    /* Total allocations */
  18. static unsigned long frees;    /* Total frees */
  19. static unsigned long garbage;    /* Total calls to free with garbage arg */
  20.  
  21. #ifdef    LARGEDATA
  22.  
  23. /**** LARGE DATA MODEL VERSION ****/
  24.  
  25. union header {
  26.     struct {
  27.         union header huge *ptr;
  28.         unsigned long size;
  29.     } s;
  30.     long l[2];
  31. };
  32.  
  33. typedef union header HEADER;
  34. #define    NULLHDR    (HEADER huge *)NULL
  35.  
  36. #define    ABLKSIZE    (sizeof (HEADER))
  37.  
  38. static HEADER huge *morecore __ARGS((unsigned nu));
  39.  
  40. static HEADER base;
  41. static HEADER huge *allocp = NULLHDR;
  42. static char huge *heapbase;
  43. static char huge *heaptop;
  44. static unsigned long heapsize;
  45.  
  46. /* Allocate block of 'nb' bytes */
  47. void *
  48. malloc(nb)
  49. unsigned nb;
  50. {
  51.     register HEADER huge *p, huge *q;
  52.     register unsigned nu;
  53.     char i_state;
  54.  
  55.     if(nb == 0)
  56.         return NULL;
  57.     i_state = dirps();
  58.     /* Round up to full block, then add one for header */
  59.     nu = ((nb + ABLKSIZE - 1) / ABLKSIZE) + 1;
  60.     if ((q = allocp) == NULLHDR){
  61.         base.s.ptr = allocp = q = &base;
  62.         base.s.size = 1;
  63.     }
  64.     for (p = q->s.ptr; ; q = p, p = p->s.ptr){
  65.         if (p->s.size >= nu){
  66.             /* This chunk is at least as large as we need */
  67.             if (p->s.size <= nu + 1){
  68.                 /* This is either a perfect fit (size == nu)
  69.                  * or the free chunk is just one unit larger.
  70.                  * In either case, alloc the whole thing,
  71.                  * because there's no point in keeping a free
  72.                  * block only large enough to hold the header.
  73.                  */
  74.                 q->s.ptr = p->s.ptr;
  75.             } else {
  76.                 /* Carve out piece from end of entry */
  77.                 p->s.size -= nu;
  78.                 p += p->s.size;
  79.                 p->s.size = nu;
  80.             }
  81.             allocp = q;
  82.             p->s.ptr = p;    /* for auditing */
  83.             restore(i_state);
  84.             allocs++;
  85.             return (void *)(p + 1);
  86.         }
  87.         /* Don't call the system for more memory if interrupts
  88.          * are off; we're probably in an interrupt handler
  89.          */
  90.         if (p == allocp && (!i_state || (p = morecore(nu)) == NULLHDR)){
  91.             memfail++;
  92.             restore(i_state);
  93.             return NULL;
  94.         }
  95.     }
  96. }
  97. /* Get more memory from the system and put it on the heap */
  98. static HEADER huge *
  99. morecore(nu)
  100. unsigned nu;
  101. {
  102.     register char huge *cp;
  103.     register HEADER huge *up;
  104.  
  105.     /* Before calling main, the Turbo startup routines call malloc to
  106.      * save the environment. In turn this calls morecore, all before we
  107.      * get a chance to call grabcore. Hence the null test for heaptop.
  108.      */
  109.     if(heaptop != NULL && (char huge *)sbrk(0) >= heaptop)
  110.         return NULLHDR;    /* Don't let it overwrite stack */
  111.     if ((int)(cp = (char huge *)sbrk(nu * ABLKSIZE)) == -1)
  112.         return NULLHDR;
  113.     up = (HEADER *)cp;
  114.     up->s.size = nu;
  115.     up->s.ptr = up;    /* satisfy audit */
  116.     free((void *)(up + 1));
  117.     return allocp;
  118. }
  119. /* Grab the specified amount of memory from the system, if available,
  120.  * and place it on the heap
  121.  */
  122. unsigned long
  123. grabcore(size)
  124. unsigned long size;
  125. {
  126.     register HEADER huge *up;
  127.  
  128.     /* Find out where the break is */
  129.     heapbase = (char huge *)sbrk(0);
  130.     /* Now try to get the requested amount, or as much as possible
  131.      * below that
  132.      */
  133.     while((int)brk(heapbase+size) == -1)
  134.         size -= 256;
  135.  
  136.     heapsize = size;
  137.     heaptop = (char huge *)sbrk(0);
  138.  
  139.     /* Initialize the heap pointers */
  140.     if (allocp == NULLHDR){
  141.         base.s.ptr = allocp = &base;
  142.         base.s.size = 1;
  143.     }
  144.     up = (HEADER *)heapbase;
  145.     up->s.size = heapsize / sizeof(HEADER);
  146.     up->s.ptr = up;    /* satisfy audit */
  147.     free((void *)(up + 1));
  148.     return heapsize;
  149. }
  150.  
  151. /* Put memory block back on heap */
  152. void
  153. free(blk)
  154. void *blk;
  155. {
  156.     register HEADER huge *p, huge *q;
  157.     unsigned short huge *ptr;
  158.     char i_state;
  159.  
  160.     if(blk == NULL)
  161.         return;        /* Required by ANSI */
  162.     i_state = dirps();
  163.     p = (HEADER huge *)blk - 1;
  164.     /* Audit check */
  165.     if(p->s.ptr != p){
  166.         ptr = (unsigned short *)&blk;
  167.         printf("WARNING!! freeing garbage (0x%lx) pc = 0x%x %x proc %s\n",ptol(blk),
  168.             ptr[-1],ptr[-2],Curproc->name);
  169.         garbage++;
  170.         restore(i_state);
  171.         return;
  172.     }
  173.     /* Search the free list looking for the right place to insert */
  174.     for(q = allocp; !(p > q && p < q->s.ptr); q = q->s.ptr){
  175.         /* Highest address on circular list? */
  176.         if(q >= q->s.ptr && (p > q || p < q->s.ptr))
  177.             break;
  178.     }
  179.     if(p + p->s.size == q->s.ptr){
  180.         /* Combine with front of this entry */
  181.         p->s.size += q->s.ptr->s.size;
  182.         p->s.ptr = q->s.ptr->s.ptr;
  183.     } else {
  184.         /* Link to front of this entry */
  185.         p->s.ptr = q->s.ptr;
  186.     }
  187.     if(q + q->s.size == p){
  188.         /* Combine with end of this entry */
  189.         q->s.size += p->s.size;
  190.         q->s.ptr = p->s.ptr;
  191.     } else {
  192.         /* Link to end of this entry */
  193.         q->s.ptr = p;
  194.     }
  195.     allocp = q;
  196.     restore(i_state);
  197.     frees++;
  198. }
  199.  
  200. #ifdef    notdef    /* Not presently used */
  201. /* Move existing block to new area */
  202. void *
  203. realloc(area,size)
  204. void *area;
  205. unsigned size;
  206. {
  207.     unsigned osize;
  208.     HEADER huge *hp;
  209.     char huge *cp;
  210.     char i_state;
  211.  
  212.     hp = ((HEADER *)area) - 1;
  213.     osize = (hp->s.size -1) * ABLKSIZE;
  214.  
  215.     /* Make sure nobody else comes in and takes it */
  216.     i_state = dirps();
  217.     free(area);
  218.     if((cp = malloc(size)) != NULL && cp != area)
  219.         memcpy((char *)cp,(char *)area,size>osize? osize : size);
  220.     restore(i_state);
  221.     return cp;
  222. }
  223. #endif
  224. /* Allocate block of cleared memory */
  225. void *
  226. calloc(nelem,size)
  227. unsigned nelem;    /* Number of elements */
  228. unsigned size;    /* Size of each element */
  229. {
  230.     register unsigned i;
  231.     register char *cp;
  232.  
  233.     i = nelem * size;
  234.     if((cp = malloc(i)) != NULL)
  235.         memset(cp,0,i);
  236.     return cp;
  237. }
  238. /* Print free list map */
  239. int
  240. memstat(argc,argv,envp)
  241. int argc;
  242. char *argv[];
  243. void *envp;
  244. {
  245.     HEADER huge *p;
  246.     unsigned long total = 0;
  247.     int i = 0;
  248.  
  249.     for(p = base.s.ptr;p != &base;p = p->s.ptr){
  250.         total += p->s.size * sizeof(HEADER);
  251.         printf("%5lx %6lu",ptol((void *)p),p->s.size * ABLKSIZE);
  252.         if(++i == 4){
  253.             i = 0;
  254.             putchar('\n');
  255.         } else
  256.             printf(" | ");
  257.     }
  258.     if(i != 0)
  259.         putchar('\n');
  260.     printf("heap base %lx size %lu avail %lu (%lu%%) coreleft %lu\n",
  261.      ptol((void *)heapbase),heapsize,total,100L*total/heapsize,
  262.      coreleft());
  263.     printf("allocs %lu frees %lu (diff %lu) mfails %lu garbage %lu\n",
  264.         allocs,frees,allocs-frees,memfail,garbage);
  265.     return 0;
  266. }
  267. #else    /* not LARGEDATA */
  268.  
  269. /**** SMALL DATA MODEL VERSION ****/
  270.  
  271. union header {
  272.     struct {
  273.         union header *ptr;
  274.         unsigned int size;
  275.     } s;
  276.     long l;
  277. };
  278.  
  279. typedef union header HEADER;
  280. #define    NULLHDR    (HEADER *)NULL
  281.  
  282. #define    ABLKSIZE    (sizeof (HEADER))
  283.  
  284. static HEADER *morecore __ARGS((unsigned nu));
  285.  
  286. static HEADER base;
  287. static HEADER *allocp = NULLHDR;
  288. static char *heapbase;
  289. static char *heaptop;
  290. static unsigned long heapsize;
  291.  
  292. /* Allocate block of 'nb' bytes */
  293. void *
  294. malloc(nb)
  295. unsigned nb;
  296. {
  297.     register HEADER *p, *q;
  298.     register unsigned nu;
  299.     char i_state;
  300.  
  301.     if(nb == 0)
  302.         return NULL;
  303.     i_state = dirps();
  304.     /* Round up to full block, then add one for header */
  305.     nu = ((nb + ABLKSIZE - 1) / ABLKSIZE) + 1;
  306.     if ((q = allocp) == NULLHDR){
  307.         base.s.ptr = allocp = q = &base;
  308.         base.s.size = 1;
  309.     }
  310.     for (p = q->s.ptr; ; q = p, p = p->s.ptr){
  311.         if (p->s.size >= nu){
  312.             /* This chunk is at least as large as we need */
  313.             if (p->s.size <= nu + 1){
  314.                 /* This is either a perfect fit (size == nu)
  315.                  * or the free chunk is just one unit larger.
  316.                  * In either case, alloc the whole thing,
  317.                  * because there's no point in keeping a free
  318.                  * block only large enough to hold the header.
  319.                  */
  320.                 q->s.ptr = p->s.ptr;
  321.             } else {
  322.                 /* Carve out piece from end of entry */
  323.                 p->s.size -= nu;
  324.                 p += p->s.size;
  325.                 p->s.size = nu;
  326.             }
  327.             allocp = q;
  328.             p->s.ptr = p;    /* for auditing */
  329.             restore(i_state);
  330.             allocs++;
  331.             return (void *)(p + 1);
  332.         }
  333.         if (p == allocp && (p = morecore(nu)) == NULLHDR){
  334.             memfail++;
  335.             restore(i_state);
  336.             return NULL;
  337.         }
  338.     }
  339. }
  340. /* Get more memory from the system and put it on the heap */
  341. static HEADER *
  342. morecore(nu)
  343. unsigned nu;
  344. {
  345.     register char *cp;
  346.     register HEADER *up;
  347.  
  348.     /* Before calling main, the Turbo startup routines call malloc to
  349.      * save the environment. In turn this calls morecore, all before we
  350.      * get a chance to call grabcore. Hence the null test for heaptop.
  351.      */
  352.     if(heaptop != NULL && (char *)sbrk(0) >= heaptop)
  353.         return NULLHDR;    /* Don't let it overwrite stack */
  354.     if ((int)(cp = (char *)sbrk(nu * ABLKSIZE)) == -1)
  355.         return NULLHDR;
  356.     up = (HEADER *)cp;
  357.     up->s.size = nu;
  358.     up->s.ptr = up;    /* satisfy audit */
  359.     free((void *)(up + 1));
  360.     return allocp;
  361. }
  362. /* Grab the specified amount of memory from the system, if available,
  363.  * and place it on the heap
  364.  */
  365. unsigned long
  366. grabcore(size)
  367. unsigned long size;
  368. {
  369.     register HEADER *up;
  370.  
  371.     /* Find out where the break is */
  372.     heapbase = (char *)sbrk(0);
  373.  
  374.     /* Now try to push it as high as possible */
  375.     while(brk(heapbase+size) == -1)
  376.         size -= 16;
  377.  
  378.     heapsize = size;
  379.     heaptop = (char *)sbrk(0);
  380.  
  381.     /* Initialize the heap pointers */
  382.     if (allocp == NULLHDR){
  383.         base.s.ptr = allocp = &base;
  384.         base.s.size = 1;
  385.     }
  386.     up = (HEADER *)heapbase;
  387.     up->s.size = heapsize / sizeof(HEADER);
  388.     up->s.ptr = up;    /* satisfy audit */
  389.     free((void *)(up + 1));
  390.     return heapsize;
  391. }
  392.  
  393. /* Put memory block back on heap */
  394. void
  395. free(blk)
  396. void *blk;
  397. {
  398.     register HEADER *p,*q;
  399.     unsigned short *ptr;
  400.     char i_state;
  401.  
  402.     if(blk == NULL)
  403.         return;        /* Required by ANSI */
  404.     i_state = dirps();
  405.     p = (HEADER *)blk - 1;
  406.     /* Audit check */
  407.     if(p->s.ptr != p){
  408.         ptr = (unsigned short *)&blk;
  409.         printf("WARNING!! freeing garbage (0x%lx) pc = 0x%x %x proc %s\n",ptol(blk),
  410.             ptr[-1],ptr[-2],Curproc->name);
  411.         garbage++;
  412.         restore(i_state);
  413.         return;
  414.     }
  415.     /* Search the free list looking for the right place to insert */
  416.     for(q = allocp; !(p > q && p < q->s.ptr); q = q->s.ptr){
  417.         /* Highest address on circular list? */
  418.         if(q >= q->s.ptr && (p > q || p < q->s.ptr))
  419.             break;
  420.     }
  421.     if(p + p->s.size == q->s.ptr){
  422.         /* Combine with front of this entry */
  423.         p->s.size += q->s.ptr->s.size;
  424.         p->s.ptr = q->s.ptr->s.ptr;
  425.     } else {
  426.         /* Link to front of this entry */
  427.         p->s.ptr = q->s.ptr;
  428.     }
  429.     if(q + q->s.size == p){
  430.         /* Combine with end of this entry */
  431.         q->s.size += p->s.size;
  432.         q->s.ptr = p->s.ptr;
  433.     } else {
  434.         /* Link to end of this entry */
  435.         q->s.ptr = p;
  436.     }
  437.     allocp = q;
  438.     restore(i_state);
  439.     frees++;
  440. }
  441.  
  442. #ifdef    notdef    /* Not presently used */
  443. /* Move existing block to new area */
  444. void *
  445. realloc(area,size)
  446. void *area;
  447. unsigned size;
  448. {
  449.     unsigned osize;
  450.     HEADER *hp;
  451.     char *cp;
  452.     char i_state;
  453.  
  454.     hp = ((HEADER *)area) - 1;
  455.     osize = (hp->s.size -1) * ABLKSIZE;
  456.  
  457.     /* Make sure nobody else comes in and takes it */
  458.     i_state = dirps();
  459.     free(area);
  460.     if((cp = malloc(size)) != NULL && cp != area)
  461.         memcpy((char *)cp,(char *)area,size>osize? osize : size);
  462.     restore(i_state);
  463.     return cp;
  464. }
  465. #endif
  466. /* Allocate block of cleared memory */
  467. void *
  468. calloc(nelem,size)
  469. unsigned nelem;    /* Number of elements */
  470. unsigned size;    /* Size of each element */
  471. {
  472.     register unsigned i;
  473.     register char *cp;
  474.  
  475.     i = nelem * size;
  476.     if((cp = malloc(i)) != NULL)
  477.         memset(cp,0,i);
  478.     return cp;
  479. }
  480. /* Print free list map */
  481. memstat(argc,argv,envp)
  482. int argc;
  483. char *argv[];
  484. void *envp;
  485. {
  486.     HEADER *p;
  487.     unsigned long total = 0;
  488.     int i = 0;
  489.  
  490.     for(p = base.s.ptr;p != &base;p = p->s.ptr){
  491.         total += p->s.size * sizeof(HEADER);
  492.         printf("%5lx %6lu",ptol(p),(long)p->s.size * ABLKSIZE);
  493.         if(++i == 4)
  494.             putchar('\n');
  495.         else
  496.             printf(" | ");
  497.     }
  498.     if(i != 0)
  499.         putchar('\n');
  500.     printf("heap base %lx size %lu avail %lu (%lu%%) coreleft %u\n",
  501.      ptol((void *)heapbase),heapsize,total,100L*total/heapsize,coreleft());
  502.     printf("allocs %lu frees %lu (diff %lu) mfails %lu garbage %lu\n",
  503.         allocs,frees,allocs-frees,memfail,garbage);
  504. }
  505. #endif
  506.  
  507.